package com.kobe.algorithm.niue;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：caopengfei
 * @date ：2021/2/26
 */
public class TreeSearch {

    static class TreeNode{
        int val = 0;
        TreeNode left= null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    public int[][] threeOrders (TreeNode root) {
        List<Integer>  frist = new ArrayList<>();
        firstSearch( root,frist );
        List<Integer>  middle = new ArrayList<>();
        middilSearch( root,middle );
        List<Integer>  after = new ArrayList<>();
        afterSearch( root,after );
        int [][] result= new int[3][];
        result[0]=listToArr(frist);
        result[1]=listToArr(middle);
        result[2]=listToArr(after);
        return result;
    }



    private int [] listToArr(List<Integer> list){
        int [] arr = new int [list.size()];
        for (int i = 0; i <list.size() ; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }


    private void  firstSearch(TreeNode tree, List<Integer> path){
        path.add(tree.val);
        if(tree.left != null){
            firstSearch(tree.left, path);
        }
        if(tree.right != null ){
            firstSearch(tree.right, path);
        }
    }

    private void  middilSearch(TreeNode tree, List<Integer> path){
        if(tree.left != null){
            middilSearch(tree.left, path);
        }
        path.add(tree.val);
        if(tree.right != null ){
            middilSearch(tree.right, path);
        }
    }

    private void  afterSearch(TreeNode tree, List<Integer> path){
        if(tree.left != null){
            afterSearch(tree.left, path);
        }
        if(tree.right != null ){
            afterSearch(tree.right, path);
        }
        path.add(tree.val);
    }
}
